package com.zwj.interview.排序;


import java.util.Arrays;

/**
 * 计数排序
 *
 * 计数排序的基本思想是先统计数组中每个整数在数组中出现的次数，
 * 然后按照从小到大的顺序将每个整数按照它出现的次数填到数组中。
 * 例如，如果输入整数数组[2，3，4，2，3，2，1]，扫描一次整个数组就能知道数组中1出现了1次，2出现了3次，3出现了2次，4出现了1次，
 * 于是先后在数组中填入1个1、3个2、2个3及1个4，就可以得到排序后的数组[1，2，2，2，3，3，4]
 *
 */
public class 计数排序 {

    public int[] sortArray(int[] nums) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        //找到数组中的最小值和最大值
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        //根据整数范围创建辅助数组counts。数组counts用来统计每个整数出现的次数
        int[] counts = new int[max - min + 1];
        //对于数组[2，3，4，2，3，2，1]，最终的counts为[1, 3, 2, 1]
        //这种做法是为了避免counts出现下标越界
        for (int num : nums) {
            counts[num - min]++;
        }
        int i = 0;
        /**
         * 在最小的数字和最大的数字之间进行遍历，因为我们是从最小的数字开始遍历的,
         * 如果某个数字num正好在数组中（counts[num-min]>0）,那么我们就将该数字
         * 放到nums数组中,下标从0开始,这样最终就实现了排序
         */
        for (int num = min; num <= max; num++) {
            while (counts[num - min] > 0) {
                nums[i++] = num;
                counts[num - min]--;
            }
        }
        return nums;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new 计数排序().sortArray(new int[]{9,8,7,6,5})));
    }
}
